package personal.leil.learning.merge;

import personal.leil.learning.utils.ArrayUtils;


/**
 * 逆序数问题
 * <p>
 * 求一个数组中逆序数的对数总和
 * 小和：数组中左侧的数字比右侧的数字大则为一对逆序数
 * 打印出所有逆序数怎么实现？
 * </p>
 *
 * @author Leil
 * @version 1.0
 * @since 2024-1-3
 */
public class InverseNumberProblem {

    public static int inverseNumber(int[] arr) {
        return process(arr, 0, arr.length - 1);
    }

    /**
     * 逆序数
     * <p>
     * 可以看成是归并排序的一个变型问题，找到所有右侧比左侧的数小的个数
     * </p>
     *
     * @param arr source array
     * @param L   left bound index for recursion
     * @param R   right bound index for recursion
     */
    public static int process(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }
        int M = L + ((R - L) >> 1);
        return process(arr, L, M)
                + process(arr, M + 1, R)
                + merge(arr, L, M, R);
    }

    /**
     * 归并-将数组降序排序
     * <p>
     * ①开辟一个足以归并数组两部分的辅助数组
     * ②当第一部分和第二部分都不越界的时候，将小的先复制到辅助数组
     * ③直到一部分越界，将另一部分全部复制到辅助数组
     * </p>
     *
     * @param arr source array
     * @param L   left bound index of left array range
     * @param M   binary index of array range
     * @param R   right bound index of right array range
     */
    public static int merge(int[] arr, int L, int M, int R) {
        int len = R - L + 1,
                l1 = L,
                r1 = M,
                l2 = M + 1,
                r2 = R,
                inverseCount = 0;
        int[] help = new int[len];
        int i = 0;
        // 这里由于左、右两侧都是有序的，而且经过merge得来的，
        // 所以只考虑左右merge的过程中，右侧比左侧小的情况就可以，
        // 右侧在l2位置小于左侧，则右侧共有r2-l2+1个数大小左侧。
        while (l1 <= r1 && l2 <= r2) {
            // print
            if (arr[l1] > arr[l2]) {
                for (int j = l2; j <= r2; j++) {
                    System.out.println("[" + arr[l1] + "," + arr[j] + "]");
                }
            }
            inverseCount += arr[l1] > arr[l2] ? (r2 - l2 + 1) : 0;
            help[i++] = arr[l1] > arr[l2] ? arr[l1++] : arr[l2++];
        }
        while (l1 <= r1) {
            help[i++] = arr[l1++];
        }
        while (l2 <= r2) {
            help[i++] = arr[l2++];
        }
        for (int h = 0; h < help.length; h++) {
            int index = L + h;
            arr[index] = help[h];
        }
        return inverseCount;
    }


    /********************* For Test *************************/

    public static void main(String[] args) {
        int[] arr = ArrayUtils.generateRandomArr(5);
        ArrayUtils.printArr(arr);
        int inverseNumber = inverseNumber(arr);
        System.out.println("inverses number count = " + inverseNumber);
        System.out.println("after process:");
        ArrayUtils.printArr(arr);
    }

}
